package top100

// 贪心策略，将最先更改位数低的位，才能保证是下一个更大的数
func nextPermutation(nums []int) {
	// 找到第一个位数小于前一位的
	for i := len(nums) - 2; i >= 0; i-- {
		if nums[i] < nums[i+1] {
			// 找到 i + 1 到 末尾位置，第一个大于它的数
			// 因为 i 是第一个大于 i+ 1位置值的，所以前面一定是 降序排列
			// 那么从后向前找第一个大于i的数
			for j := len(nums) - 1; j > i; j-- {
				if nums[j] > nums[i] {
					// 交换
					nums[i], nums[j] = nums[j], nums[i]
					break
				}
			}
			// 如例子 [1,3,2] 交换后为 [2,3,1] 交换后 i 后顺序还是 可以排列的
			// 将 i 后面的序列，逆序。 因为肯定是 递减的，很好理解，逆序变为最小值，递增
			reverse(nums, i+1, len(nums)-1)
			break
		}
		// 不存在下一个更大的，那么数组必然是降序排列，返回升序的为最小
		if i == 0 {
			reverse(nums, 0, len(nums)-1)
		}
	}
}

// 反转
func reverse(nums []int, i, j int) {
	for i < j {
		nums[i], nums[j] = nums[j], nums[i]
		j--
		i++
	}
}
